1. Field of the Invention
The present invention relates generally to communication devices, and specifically, to an apparatus and method for classifying information received by communications devices.
2. Background Information
Small and medium businesses typically have networks comprised of local area networks ("LANs"), ranging between 10 Mega bits per second ("Mbps") to 100 Mbps, that carry information between stations for a wide range of applications. The applications can include a mixture of voice, video, interactive, web browsing, file transfers, etc., each of which has different minimum requirements for latency, jitter, and data loss to ensure quality communication. The internal office LANs can either provide sufficient bandwidth or are economically upgradable to provide an order of magnitude increase in bandwidth.
The connection to a wide area network ("WAN") is however another matter. The bandwidth is not easily upgradable due to the cost of WAN access circuits. Various queuing techniques have been employed in WAN access equipment in attempts to provide sharing of the limited circuit bandwidth among the different types of data. These queuing techniques typically have limited applications and undesirable characteristics. For example, in one queuing technique, queues are serviced in strict priority order, which tends to starve low priority data types. Another technique, called Weighted Fair Queuing, solves the starvation effects but it is computational intensive and does not provide guaranteed bandwidth, delay bound or jitter bound characteristics for data types that need these characteristics.
In implementing such queuing techniques, incoming data must first been identified and thereafter, classified for queuing allocation. Current routers, which provide some form of classification system, do so by combining search technologies previously used for routing table lookups. These technologies rely on algorithms such as the Patricia tree (as described by Don Morrison in "Practical Algorithm to Retrieve Information Coded In Alfanumeric," Journal of the ACM, October 1968), or the Lulea tree (as described by Mikael Degermark of the Lulea University of Technology in "Small Forwarding Tables for Fast Routing Lookups," Computer Communications Review, October 1998), search algorithms to perform lookup operations of various portions of the internet protocol (IP) header. The results from these searches are combined in some fashion (e.g., using Cross Product tables or arrays, as described by V. Srinivasan of Washington University in "Fast and Scalable Layer Four Switching," Computer Communications Review, October 1998) and used to formulate a "class" for the incoming data.
Existing routing search algorithms are used to handling definitions of the form "Address A=route n". To apply an existing routing search technique for searching and classifying data in ranges, "n" individual search steps have to be used. This results in excess data storage space requirements, and additional processing requirements when handling classification ranges.
Since the number of possible resulting combinations can be immense, the problem of translating the search results to a "class" is not trivial. Traditional approaches use either a simple array or something like a Cross Product table (as described by V. Srinivasan of Washington University in "Fast and Scalable Layer Four Switching," Computer Communications Review, October 1998.
Simple arrays, although fast, require memory to hold every possible combination, so are impractical except for the simplest cases. The problem associated with using Cross Product tables to locate the final "class" results is that the most recently accessed results must be cached in the Cross Product table. Basically, the results from each individual search are combined by an expression similar to "finalResult=(((((((result1 * maxResult1)+result2) * maxResult2)+result3) * maxResult3)+result4) * maxResult4)+result5". The final "cross product" value is searched for in the "key" column of the Cross Product table, using a binary search. If the value is found, the correspond "result" column entry is returned as the "class" value. If not found, which is more likely to be the case due to the large range of possible values, a exhaustive search of the available classes must be done. The found "class" and the "cross product" value are both added to the "Cross Product" table. Although a Cross Product table does minimize the amount of memory required, processing requirements become nondeterministic.
Accordingly, there is a need in the technology for classifying incoming data received by a communications device that overcomes the aforementioned problems.
To classify incoming data, searches are typically performed to identify incoming data such as network frames or protocol data units. Traditional search methods either required each unique value to be explicitly stored in a search tree, or required an elaborate tree structure such as the use of a "grid of tries" to provide an efficient search. Since the search has to operate very quickly (typically less than one microsecond on the average), it is imperative to utilize the full capabilities of the processor in the communications device. For such traditional search techniques to operate efficiently, all data that has to be searched is typically stored in the processor's memory space. However, since the processor has only limited amounts of internal memory, the implementation of such traditional search techniques are not practicable.
Moreover, such in using such traditional search techniques, the average and worst case execution times do not remain deterministic beyond a small number of search values. These values are those that are located in the processor's memory space.
Accordingly, there is a need in the technology for an apparatus and method for identifying incoming data received by a communications device that overcomes the aforementioned problems.